// Copyright (c) 2005-2008, Simon Howard
// Permission to use, copy, modify, and/or distribute this software
// for any purpose with or without fee is hereby granted, provided
// that the above copyright notice and this permission notice appear
// in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
// WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
// AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
// CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
// NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

use std::collections::HashSet;
use std::hash::{Hash, Hasher};
use std::mem;

// A simple wrapper around HashSet to provide additional functionality
// like registering a free function and tracking allocated values.
pub struct Set<T> {
    inner: HashSet<T>,
    free_fn: Option<Box<dyn Fn(T)>>,
}

impl<T> Set<T>
where
    T: Eq + Hash,
{
    /// Creates a new empty set.
    pub fn new() -> Self {
        Set {
            inner: HashSet::new(),
            free_fn: None,
        }
    }

    /// Inserts a value into the set.
    pub fn insert(&mut self, value: T) -> bool {
        self.inner.insert(value)
    }

    /// Checks if the set contains a value.
    pub fn contains(&self, value: &T) -> bool {
        self.inner.contains(value)
    }

    /// Removes a value from the set.
    pub fn remove(&mut self, value: &T) -> bool {
        self.inner.remove(value)
    }

    /// Returns the number of elements in the set.
    pub fn len(&self) -> usize {
        self.inner.len()
    }

    /// Registers a free function to be called when the set is dropped.
    pub fn register_free_function<F>(&mut self, free_fn: F)
    where
        F: Fn(T) + 'static,
    {
        self.free_fn = Some(Box::new(free_fn));
    }
}

impl<T> Drop for Set<T> {
    fn drop(&mut self) {
        if let Some(free_fn) = &self.free_fn {
            for value in self.inner.drain() {
                free_fn(value);
            }
        }
    }
}

// Global counter for allocated values.
static mut ALLOCATED_VALUES: i32 = 0;

/// Creates a new integer value and increments the allocated values counter.
fn new_value(value: i32) -> i32 {
    unsafe {
        ALLOCATED_VALUES += 1;
    }
    value
}

/// Frees an integer value and decrements the allocated values counter.
fn free_value(_value: i32) {
    unsafe {
        ALLOCATED_VALUES -= 1;
    }
}

#[test]
fn test_set_new_free() {
    let mut set = Set::new();
    set.register_free_function(free_value);

    assert_eq!(set.len(), 0);

    for i in 0..10000 {
        set.insert(new_value(i));
    }

    assert_eq!(set.len(), 10000);

    // Dropping the set should free all values.
    unsafe {
        assert_eq!(ALLOCATED_VALUES, 10000);
    }
    mem::drop(set);
    unsafe {
        assert_eq!(ALLOCATED_VALUES, 0);
    }
}

#[test]
fn test_set_insert() {
    let mut set = Set::new();

    let numbers1 = [1, 2, 3, 4, 5, 6];
    let numbers2 = [5, 6, 7, 8, 9, 10];

    for &num in numbers1.iter() {
        set.insert(num);
    }
    for &num in numbers2.iter() {
        set.insert(num);
    }

    assert_eq!(set.len(), 10);
}

#[test]
fn test_set_query() {
    let mut set = Set::new();

    for i in 0..10000 {
        set.insert(format!("{}", i));
    }

    for i in 0..10000 {
        assert!(set.contains(&format!("{}", i)));
    }

    assert!(!set.contains("-1"));
    assert!(!set.contains("100001"));
}

#[test]
fn test_set_remove() {
    let mut set = Set::new();

    for i in 0..10000 {
        set.insert(format!("{}", i));
    }

    assert_eq!(set.len(), 10000);

    for i in 4000..6000 {
        let key = format!("{}", i);
        assert!(set.contains(&key));
        assert!(set.remove(&key));
        assert!(!set.contains(&key));
    }

    assert_eq!(set.len(), 8000);

    for i in -1000..-500 {
        assert!(!set.remove(&format!("{}", i)));
    }

    for i in 50000..51000 {
        assert!(!set.remove(&format!("{}", i)));
    }
}

#[test]
fn test_set_union() {
    let mut set1 = Set::new();
    let mut set2 = Set::new();

    let numbers1 = [1, 2, 3, 4, 5, 6, 7];
    let numbers2 = [5, 6, 7, 8, 9, 10, 11];

    for &num in numbers1.iter() {
        set1.insert(num);
    }
    for &num in numbers2.iter() {
        set2.insert(num);
    }

    let mut result_set = Set::new();
    for &num in set1.inner.union(&set2.inner) {
        result_set.insert(*num);
    }

    assert_eq!(result_set.len(), 11);
}

#[test]
fn test_set_intersection() {
    let mut set1 = Set::new();
    let mut set2 = Set::new();

    let numbers1 = [1, 2, 3, 4, 5, 6, 7];
    let numbers2 = [5, 6, 7, 8, 9, 10, 11];

    for &num in numbers1.iter() {
        set1.insert(num);
    }
    for &num in numbers2.iter() {
        set2.insert(num);
    }

    let mut result_set = Set::new();
    for &num in set1.inner.intersection(&set2.inner) {
        result_set.insert(*num);
    }

    assert_eq!(result_set.len(), 3);
}

#[test]
fn test_set_to_array() {
    let mut set = Set::new();

    let values = [1; 100];
    for &value in values.iter() {
        set.insert(value);
    }

    let array: Vec<_> = set.inner.iter().collect();
    assert_eq!(array.len(), 1);
    assert_eq!(*array[0], 1);
}

#[test]
fn test_set_iterating() {
    let mut set = Set::new();

    for i in 0..10000 {
        set.insert(format!("{}", i));
    }

    let mut count = 0;
    for _ in set.inner.iter() {
        count += 1;
    }

    assert_eq!(count, 10000);
}

#[test]
fn test_set_iterating_remove() {
    let mut set = Set::new();

    for i in 0..10000 {
        set.insert(format!("{}", i));
    }

    let mut count = 0;
    let mut removed = 0;

    for key in set.inner.iter() {
        let value = key.parse::<i32>().unwrap();
        if value % 100 == 0 {
            set.remove(key);
            removed += 1;
        }
        count += 1;
    }

    assert_eq!(count, 10000);
    assert_eq!(removed, 100);
    assert_eq!(set.len(), 9900);
}

#[test]
fn test_set_free_function() {
    let mut set = Set::new();
    set.register_free_function(free_value);

    unsafe {
        assert_eq!(ALLOCATED_VALUES, 0);
    }

    for i in 0..1000 {
        set.insert(new_value(i));
    }

    unsafe {
        assert_eq!(ALLOCATED_VALUES, 1000);
    }

    set.remove(&500);

    unsafe {
        assert_eq!(ALLOCATED_VALUES, 999);
    }

    mem::drop(set);

    unsafe {
        assert_eq!(ALLOCATED_VALUES, 0);
    }
}
